package leetCode.offer68_ii;


import java.util.Stack;

/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 */
public class Solution1 implements Solution{


    /**
     * 解题思路：
     * 特殊情况，首先检查p,q是否是父子关系
     * 如果不是父子关系，那么p,q肯定分别属于最近祖先节点的左右子树中
     * 那么就可以根据遍历来检查每个节点是否是p,q的父节点来完成
     * @param root
     * @param p
     * @param q
     * @return
     */
    @Override
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(isContains(p,q)) return p;
        if(isContains(q,p)) return q;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            //这里是解题的关键
            if(cur.right!=null&&cur.left!=null){
                if(isContains(cur.left,p)&&isContains(cur.right,q)||
                        isContains(cur.right,p)&&isContains(cur.left,q)){
                    return cur;
                }
            }
            if(cur.left!=null) stack.add(cur.left);
            if(cur.right!=null) stack.add(cur.right);
        }

        return null;
    }

    /**
     * 判断指定节点root是否包含son节点
     * @param root
     * @param son
     * @return
     */
    boolean isContains(TreeNode root,TreeNode son) {
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.val == son.val){
                return true;
            }
            if(cur.left!=null) stack.add(cur.left);
            if(cur.right!=null) stack.add(cur.right);
        }
        return false;
    }


}
